The present invention concerns the modification of a Single Instruction Multiple Datastream (SIMD) polymorphic mesh network array processing system by the inclusion of a Single Instruction Multiple Address (SIMA) mechanism including a content addressable packet buffer memory to enable processing by an algorithm representing an arbitrary graph rather than algorithms representing predetermined graphs.
In network design, a primary objective is to increase the speed of transmitting an instruction or performing a task while concurrently creating more network parallelism. In a preferred embodiment of the present invention, a fourth degree Single Instruction Multiple Datastream network array of conventional polymorphic mesh configuration is modified by a Single Instruction Multiple Address mechanism without altering the mesh network interconnection, in order to provide increased speed and network parallelism than in heretofore known arrangements.
In pending U.S. patent application Ser. No. 06/902,343 filed Aug. 29, 1986, now abandoned, in continuation application Ser. No. 07/208,850, filed Jun. 20, 1988, now U.S. Pat. No. 5,038,386, a polymorphic mesh network is described for a SIMD parallel architecture containing n x n processing elements interconnected physically by a mesh network within each processing element, wherein a polymorphic controller allows the architecture to dynamically derive many conventional graphs such as a tree, pyramid, cube and the like under instruction control. There is relatively low parallelism if the affected processing elements are not adjacent.
The SIMD generated graphs cover a wide spectrum of algorithms useful in image processing, computer vision and graphic applications. However, there are algorithms in these applications and others that are beyond conventional graphs and can only be represented by an arbitrary graph.
There is no general parallel architecture capable of matching all possible graphs since each algorithm results in a unique type of graph. The present invention describes several methods and a circuit which allow the processing elements in a polymorphic mesh architecture to establish communication between each other as prescribed by an arbitrary graph. The invention provides for buffer memory to address all processing elements having a matching address. This feature is the single instruction multiple address feature.
A SIMA circuit containing a two-dimensional memory, a priority circuit and a register, interacts with the polymorphic mesh network of processing elements through a data line. A controller provides address and mode signals. Polymorphic mesh processing requires each processing element to exchange with or deliver to its row or column neighbor information. The movement is guided by a packet which comprises an address and data. The SIMA circuit creates N addresses each of which points to the buffer memory that contains a packet having the proper bit value in the i-th position of the address. Packet exchanging or delivery is performed according to the transfer method employed.
Content-addressable-memory and two-dimensional memory are known to those skilled in the art. The use of a content-addressable memory to derive multiple addresses from a single instruction in a single instruction multiple datastream array processor is where the present invention resides, particularly as applied to packet exchange and delivery.